package com.ywgt;

import java.util.ArrayList;

/**
 * 克鲁斯卡尔算法，公交车站点问题
 */
public class Kruskal {

    static final int N=1000;
    public static void main(String[] args) {
        char[] points={'A','B','C','D','E','F','G'};
        int [][] diatance=new int[points.length][points.length];
        diatance[0]=new int[]{0,12,N,N,N,16,14};
        diatance[1]=new int[]{12,0,10,N,N,7,N};
        diatance[2]=new int[]{N,10,0,3,5,6,N};
        diatance[3]=new int[]{N,N,3,0,4,N,N};
        diatance[4]=new int[]{N,N,5,4,0,2,8};
        diatance[5]=new int[]{16,7,6,N,2,0,9};
        diatance[6]=new int[]{14,N,N,N,8,9,0};
        Model model=new Model(points,diatance);
        model.print();
        model.getMinTree();

    }
}

class Model{
    char[] point;
    int edgesNum;
    int [] [] weight;

    public Model(char[] point,int[][] weight) {
        this.point = point;
        this.weight = weight;
        for (int i = 0; i < weight.length; i++) {
            for (int j = i+1; j < weight[i].length; j++) {
                if(1000!=weight[i][j]){
                    edgesNum++;
                }
            }
        }
    }

    /**
     * 生成最小树
     */
    public void getMinTree(){
        int index=0;
        int ends[]=new int[edgesNum]; //保存每个节点的终点信息
        Edge[] res=new Edge[edgesNum]; //结果集
        Edge[] edges = getEdges(); //获取边的集合
        sortEdges(edges); //将集合按照每个边的权值从小到大排序
        for (int i = 0; i < edgesNum; i++) {
            Edge edge = edges[i];  //拿到最小权值的边
            int pos1 = getPosition(edge.a); //拿到这个点在集合中的顺序
            int pos2 = getPosition(edge.b);
            int end1 = getEnd(ends, pos1);//获取这个点的终点
            int end2 = getEnd(ends, pos2);
            if(end1!=end2){ //判断两个点的终点是否指向了同一个点
                ends[end1]=end2;  //如果不相等，则将边的端点的终点设置为边的终点
                res[index++]=edge;//放入集合，并对index++
            }
        }
        for (Edge re : res) {
            System.out.print(re==null?"":re);
        }
    }

    /**
     * 根据下标获取对应点的终点下标
     * @param ends
     * @param index
     * @return
     */
    public int getEnd(int [] ends,int index){
        while(ends[index]!=0){
            index=ends[index];
        }
        return index;
    }

    /**
     * 获取当前char对应的位置
     * @param c
     * @return
     */
    public int getPosition(char c){
        for (int i = 0; i < point.length; i++) {
            if(point[i]==c){
                return i;
            }
        }
        return -1;
    }

    public void print(){
        for (int i = 0; i < weight.length; i++) {
            for (int j = 0; j < weight[i].length; j++) {
                System.out.printf("%10d",weight[i][j]);
            }
            System.out.println();
        }
        System.out.println("一共"+edgesNum+"条边");
    }

    /**
     * 对所有的边进行排序，从小到大
     * @param edges
     */
    public void sortEdges(Edge[] edges){
        for (int i = 0; i < edges.length-1; i++) {
            for (int j = 0; j < edges.length-1-i; j++) {
                if(edges[j].weight>edges[j+1].weight){
                    Edge edge=edges[j+1];
                    edges[j+1]=edges[j];
                    edges[j]=edge;
                }
            }
        }
        for (Edge edge : edges) {
            System.out.println(edge);
        }

    }

    /**
     * 根据权值表，生成边集合
     * @return
     */
    public Edge[] getEdges(){
        int index=0;
        Edge[] edges=new Edge[edgesNum];
        for (int i = 0; i < weight.length; i++) {
            for (int j =i+ 1; j < weight[i].length; j++) {
                if(weight[i][j]<1000){
                    edges[index]=new Edge(point[i],point[j],weight[i][j]);
                    index++;
                }
            }
        }
        return edges;
    }
}

class Edge{
    char a;
    char b;
    int weight;

    public Edge(char a, char b, int weight) {
        this.a = a;
        this.b = b;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Edge{" +
                 a +"->"+
                b +
                ", " + weight +
                '}';
    }
}
